离开中山路
题目 离开中山路
思路分析
给定起点和终点
代码实现
0~n-1
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=1010;
char g[N][N];
int d[N][N];
int n;
int x2,y2;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n-1 && y>=0 && y<=n-1 && d[x][y]==-1;
}
int bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
q.push({x,y});
d[x][y]=0;
while(!q.empty()){
auto cur=q.front();
int ux=cur.first,uy=cur.second;
q.pop();
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]=='0'){
d[nx][ny]=d[ux][uy]+1;
q.push({nx,ny});
}
}
}
return d[x2][y2];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
cin>>g[i];
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++)
// cout<<g[i][j]<<" ";
// cout<<endl;
// }
int x,y;
cin>>x>>y>>x2>>y2;
x-=1,y-=1,x2-=1,y2-=1;
// cout<<"x1: "<<x<<" y1: "<<y<<" x2: "<<x2<<" y2: "<<y2<<endl;
cout<<bfs(x,y)<<endl;
return 0;
}
1~n
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=1010;
char g[N][N];
int d[N][N];
int n;
int x2,y2;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=1 && x<=n && y>=1 && y<=n && d[x][y]==-1;
}
int bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
q.push({x,y});
d[x][y]=0;
while(!q.empty()){
auto cur=q.front();
int ux=cur.first,uy=cur.second;
q.pop();
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]=='0'){
d[nx][ny]=d[ux][uy]+1;
q.push({nx,ny});
}
}
}
return d[x2][y2];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>g[i]+1;
int x,y;
cin>>x>>y>>x2>>y2;
cout<<bfs(x,y)<<endl;
return 0;
}
💬 评论